package newcoder_exp.meituan;

import org.junit.Test;
import java.util.*;

import utils.BracketUtils;

public class Meituan9 {
    
    // 1.字母移位
    public String moveString(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c: s.toCharArray()) {
            if (c == 'a') {
                sb.append('z');
            } else {
                sb.append((char)(c - 1));
            }
        }
        return sb.toString();
    }

    @Test
    public void test1() {
        String s = "abundun";
        System.out.println(moveString(s));
    }

    // 2. N*N的方格最多能放多少个矩阵，方格中存在障碍物【】
    // 改：力扣85 最大矩形 ：给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
    
    /* 
        对于每一层元素，相当于Ex84的最大矩形
    */
    class Solution85 {
        public int maximalRectangle(String[][] matrix) {
            int m = matrix.length, n = matrix[0].length;
            int[][] nums = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    nums[i][j] = matrix[i][j] == "1" ? 1 : 0;
                    if (i == 0 || nums[i - 1][j] == 0) {
                       nums[i][j] += 0;
                    } else if (nums[i][j] != 0) {
                        nums[i][j] += nums[i - 1][j];
                    }
                }
            }
            int res = 0;
            Stack<Integer> stack = new Stack<>();
            for (int i = 0; i < m; i++) {
                stack.clear();
                int[] newArray = new int[n + 2];
                System.arraycopy(nums[i], 0, newArray, 1, n);
                newArray[0] = 0;
                newArray[n + 1] = 0;
                //首尾默认为0
                for (int j = 0; j < n + 2; j++) {
                    while (!stack.isEmpty() && newArray[stack.peek()] > newArray[j]) {
                        int cur = stack.pop();
                        int left = stack.peek();//stack.isEmpty() ? 0 : stack.peek();
                        int width = j - left - 1;
                        res = Math.max(res, width * newArray[cur]);
                    }
                    stack.push(j);
                }
            }
            return res;
        }
    }

    @Test
    public void test3() {
        // [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"]["1","0","0","1","0"]]
        String[][] chars = new String[4][];
        chars[0] = new String[]{"1","0","1","0","0"};
        chars[1] = new String[]{"1","0","1","1","1"};
        chars[2] = new String[]{"1","1","1","1","1"};
        chars[3] = new String[]{"1","0","0","1","0"};
        Solution85 s = new Solution85();
        System.out.println(s.maximalRectangle(chars));
    }

    // 3.植物大战僵尸

    // 4. 买卖股票[冷冻期lc:309]
    class Solution309 {

        /* 
            0:没卖，不持有
            1：持有
            2：卖了，不持有

            这样的方法也可以改为递归解
        */
        public int maxProfit(int[] prices) {
            int[] nums = prices;
            int len = nums.length;
            int[][] f = new int[len][3];
            f[0][0] = 0; //没有也没买
            f[0][1] = -prices[0]; //买了
            f[0][2] = 0; //买了又卖了

            for (int i = 1; i < len; i++) {
                f[i][0] = Math.max(f[i - 1][0], f[i - 1][2]); //昨天卖了，我无法买；昨天没买，今天依然不想买
                f[i][1] = Math.max(f[i - 1][1], f[i - 1][0] - nums[i]);
                f[i][2] = f[i - 1][1] + nums[i];
            }

            return Math.max(f[len - 1][0],f[len - 1][2]);
        }
    }

    @Test
    public void test2() {
        Solution309 s = new Solution309();
        int[] nums = new int[]{1,2,3,0,2};
        System.out.println(s.maxProfit(nums));
    }


    //6. 得到网格中最小路径并输出路径
    public int minPathSum(int[][] grid) {       
        int m = grid.length, n = grid[0].length;
        int[][] f = new int[m][n];
        int[] path = new int[m * n];
        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                f[i][j] = grid[i][j];
                if (i == m - 1 && j == n - 1) {
                    f[i][j] += 0;
                } else if (i == m - 1) {
                    f[i][j] += f[i][j + 1];
                    path[i * m + j] = i * m + j + 1;
                } else if (j == n - 1) {
                    f[i][j] += f[i + 1][j];
                    path[i * m + j] = (i + 1) * m + j;
                } else {
                    f[i][j] += Math.min(f[i + 1][j], f[i][j + 1]);
                    if (f[i + 1][j] <= f[i][j + 1]) {
                        path[i * m + j] = (i + 1) * m + j;
                    } else {
                        path[i * m + j] = i * m + j + 1;
                    }
                }
            }
        }
        int cur = 0;
        int end = (m - 1) * m + n - 1;
        int idx = 0;
        this.m = m;
        this.n = n;
        while (cur <= end) {
            int[] p = from1Dto2D(cur);
            System.out.printf("当前为第%d步，经过点了点<%d, %d>, 其值为%d\n", idx++, p[0], p[1], grid[p[0]][p[1]]);
            cur = path[p[0] * m + p[1]];
        }
        return f[0][0];
    }

    int m, n;
    public int[] from1Dto2D(int cur) {
        int i = cur / m, j = cur % n;
        return new int[]{i, j};
    }

    @Test
    public void test6() {
        int[][] nums = BracketUtils.to2DArray("[[1,3,1],[1,5,1],[4,2,1]]");
        System.out.println(minPathSum(nums));
    }

}
